"""
Problem 87: https://projecteuler.net/problem=87

能表示成一个质数的平方加一个质数的立方再加一个质数的四次方的和的最小整数是28。
实际上, 在50以下只有4个整数能表示成这种形式。

    28 = 2^2 + 2^3 + 2^4
    33 = 3^2 + 2^3 + 2^4
    49 = 5^2 + 2^3 + 2^4
    47 = 2^2 + 3^3 + 2^4

在5000,0000以下共有多少个整数能用如上形式表示出来呢?
"""


from commonfuncs.primefunctools import primesTable
pt = primesTable(4)
primes = [i for i in range(len(pt)) if pt[i]]
# print(primes)
primes_pow2 = [p**2 for p in primes]
primes_pow3 = [p**3 for p in primes]
primes_pow4 = [p2**2 for p2 in primes_pow2]


def solution(limit: int = 50000000) -> int:
    """
    d = d2^2 + d3^3 + d4^4

    d2 < limit**(1/2)
    d3 < limit**(1/3)
    d4 < limit**(1/4)
    """
    res = set()

    for d22 in primes_pow2:
        if d22 >= limit:
            break
        for d33 in primes_pow3:
            if d22 + d33 >= limit:
                break
            for d44 in primes_pow4:
                d = d22 + d33 + d44
                if d < limit:
                    # print(f'd22={d22},d33={d33},d44={d44}')
                    res.add(d)
                else:
                    break
    return len(res)


if __name__ == "__main__":
    from doctest import testmod

    testmod()
    print(solution())
    # 1097343
